/**
* Created with CLion.
* User:Lenovo
* Date:2023-05-22
* Time:4:05
* Description:洛谷 P1706  全排列问题
*/

#include <stdio.h>

void dfs(int n, int i, int *used, int *ans) // used 数组记录数字是否被使用过，ans 数组记录答案，i 表示现在是答案的第几个数
{
    if (i == n) // ans 数组已经被填满，此时打印答案
    {
        for (int k = 0; k < n; k++)
        {
            printf("%5d", ans[k]);
        }
        printf("\n");
    }
    else // ans 数组没被填满
    {
        for (int m = 1; m <= n; m++) // 数字从 1 - 9
        {
            if (used[m] == 0)
            {
                used[m] = 1;
                ans[i] = m;
                dfs(n, i + 1, used, ans);// 继续填下一个数
                used[m] = 0;// 如果运行到这里，说明前面的答案已经被输出，此时进行回溯操作，也就是把 m 设置成没有使用过
            }
        }
    }
    // 运行到这里，说明 1 - n 全都循环完毕，此时函数结束，返回到上一个递归，于是上一个数的 used 也会被设成 0
}

int main()
{
    int n;
    scanf("%d", &n);
    int ans[n];
    int used[n + 1];
    for (int i = 1; i <= n; i++)
    {
        used[i] = 0;
    }
    dfs(n, 0, used, ans);

    return 0;
}